package com.fantaike.algorithm.symbol;

import lombok.Data;
import org.w3c.dom.Node;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;

/**
 * 有序符号表
 * @author jishushen
 * @create 2021-11-02 21:48
 */
public class OrderSymbolTable<Key extends Comparable<Key>,Value> implements Iterable{
    //记录首节点的位置
    private Node head;
    //元素的个数
    private int N;

    @Data
    public class Node{
        //键
        public Key key;
        //值
        public Value value;
        //下一个节点
        private Node next;

        public Node(Key key, Value value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    public OrderSymbolTable(){
        head = new Node(null,null,null);
        N = 0;
    }

    //获取元素的个数
    public int size(){
        return N;
    }

    //向符号表中进行插入
    public void put(Key key,Value value){
        //定义两个变量分别记录当前节点和当前节点的上一个节点
        Node curr = head.next;
        Node pre = head;
        //当前节点不为空，并且传来的key大于当前节点的key继续循环
        while (curr != null && key.compareTo(curr.key) > 0){
            //变换当前节点及上一个节点
            pre = curr;
            curr = curr.next;
        }
        //如果当前节点不为null,并且传来的key和当前节点的key相等则进行替换同一key的值
        if (curr != null && curr.key.equals(key)){
            curr.value = value;
            //结束方法
            return;
        }
        //当前节点的key和要插入节点的key的值不相等，那么就将新的节点插入到当前节点之前
        Node newNode = new Node(key,value,curr);
        //上一个节点的下一个节点为新插入的节点
        pre.next = newNode;
        //元素个数+1
        N++;
    }

    //删除符号表中键为Key的值
    public void delete(Key key){
        //将head赋值给一个变量进行遍历
        Node n = head;
        //进行遍历，找到键为key值删除掉
        while (n.next != null){
            if (n.next.key.equals(key)){
                //将n的下一个节点指向下下节点
                n.next = n.next.next;
                //元素个数减-
                N--;
                return;
            }
            //变换n
            n = n.next;
        }
    }

    //从符号表中获取key对应的value
    public Value get(Key key){
        //将head赋值一个变量
        Node n = head;
        while (n.next != null){
            //变换n
            n = n.next;
            //如果key相等就将value返回去
            if (n.key.equals(key)){
                return n.value;
            }
        }
        return null;
    }

    @Override
    public Iterator iterator() {
        return new SIterator();
    }

    private class SIterator implements Iterator{

        private Node node;

        public SIterator(){
            this.node = head;
        }

        @Override
        public boolean hasNext() {
            return node.next != null;
        }

        @Override
        public Object next() {
            node = node.next;
            return new HashMap<Key,Value>(){{
                put(node.key,node.value);
            }};
        }
    }
}
